augmented_containers::​augmented_graph_t

enum class augmented_graph_part_data_structure_e {
	top_tree,
	link_cut_tree,
	a_new_approach_to_dynamic_all_pairs_shortest_paths,
	fully_dynamic_planarity_testing_in_polylogarithmic_time, };
template<
	typename vertex_t,
	typename edge_t,
	typename parts_data_structure_and_parameters_t,
	std::strict_weak_order<vertex_t, vertex_t> compartor_vertex_t = std::less<vertex_t>,
	std::strict_weak_order<edge_t, edge_t> compartor_edge_t = std::less<edge_t>,
	typename allocator_vertex_t = std::allocator<vertex_t>
> struct augmented_graph_t;

augmented_graph_t is an augmented, general-purpose graph. It's part of the augmented containers library, providing a more powerful version of containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input changes, refresh output values/ranges in logarithmic time complexity). To help understand what kind of problems the library solves: Dynamic problem (algorithms) - Wikipedia, Augmented map - Wikipedia.

• augmented_graph_t logically treat vertex set and edge set as ordered multisets, thus the interface for iterating, searching, inserting and erasing vertices and edges is similar to std::multiset/multimap. augmented_graph_t maintains each vertex's incident edge set and each vertex pair's edge set.
• augmented_graph_t allows updating vertices and edges using a user-supplied functor. For vertex set and edge set, this is just extracting the node, calling update functor on the value and inserting the node back to std::multiset/multimap. The other data structures (e.g. each vertex's incident edge set, each vertex pair's edge set, top trees) stores vertex iterators and edge iterators ordered by the addresses of the elements they point to when possible, so they are not affected by the update operation.
• augmented_graph_t has at least zero parts. Each part efficiently maintains information about some property/invariant on the graph subject to dynamic changes (vertex&edge insert&erase&update), processes queries on the property/invariant quickly and performs update operations faster than recomputing from scratch, as carried out by the fastest static algorithm.
  • augmented_graph_part_data_structure_e::top_tree implements the top tree in "Design and Analysis of Data Structures for Dynamic Trees", can be used to maintain some properties/invariants of graphs/trees.
    For each non-trivial tree in the original forest (or a induced forest of the original graph), top tree logically maintains a sequence of trees, the number of which is logarithmic with respect to tree size. The first tree is the original tree. Each subsequent tree is a contracted version of the previous tree. The last tree is an edge.
    A sequence of rake and compress operations transforms a tree into a contracted version. When v1 has degree 1 and v1 is the predecessor of v3 in v2's adjacent vertices' circular order, cluster<v1,v2> can be raked onto cluster<v2,v3> resulting in cluster<v2,v3> (v1v2⤻v2v3＝v2v3). When v2 has degree 2, cluster<v1,v2> can be compressed with cluster<v2,v3> resulting in cluster<v1,v3> (v1v2→←v2v3=v1v3).
    Top tree logically allows to link two trees by an edge into one and cut one tree by an edge into two. augmented_graph_part_data_structure_e::top_tree also physically maintains the set of vertices with no incident edges and the set of edges that do not belong to the forest. User-supplied internal_operations_t should provide 4 operations (create, destroy, join, split) to maintain cluster_t of each cluster. internal_operations_t can optionally provide edge_to_be_replaced, so that when inserting an edge whose 2 vertices belong to the same tree, to select a tree edge to cut before link the edge as a tree edge, or to not select any edge and just put the edge to the set of edges that do not belong to the forest. internal_operations_t can optionally provide comparator_it_edge_it_vertexes_t to order the set of edges that do not belong to the forest, so that when eraseing a tree edge, to determine the order of examination of edges (if the edge's 2 vertices belong to 2 different trees, link the edge as a tree edge).

Examples

empty

Each vertex_t/edge_t(std::monostate) does not store any information. No parts are attached to the graph. Only structual information of the graph is maintained.

augmented_containers::augmented_graph_t<
	std::monostate,
	std::monostate,
	std::tuple<>,
	monostate_comparator_t,
	monostate_comparator_t
> augmented_graph;

arbitrary_spanning_forest

A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t(void) does not store any information. The internal operation does not suggest any tree edge to cut when inserted edge's 2 vertices belong to same tree. An arbitrary spanning forest of the graph is maintained, so circuit rank (cyclomatic number), a cycle basis and a feedback edge set of the graph can be answered quickly. Connected components of the graph and whether 2 vertices belong to same component can also be answered quickly, but note that there are faster data structures dedicated to maintaining connectivity information of graphs.

augmented_containers::augmented_graph_t<
    std::monostate,
    std::monostate,
    std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_empty_t<>>
    >,
    monostate_comparator_t,
    monostate_comparator_t
> augmented_graph;

minimum_spanning_forest

Each edge_t(int) stores the weight of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t(graph_t::it_edge_it_vertex_t) points to the maximum-weight edge among the cluster's path descendant edges.

When inserting an edge whose 2 vertices belong to same tree, augmented_graph_part_data_structure_e::top_tree exposes the 2 vertices (so the iterator pointing to the maximum-weight edge among the tree path's edges can be read from root cluster). get_top_tree_internal_operations_selecting_path_t selects the old edge for augmented_graph_part_data_structure_e::top_tree to cut before linking the new edge, or doesn't select any edge and augmented_graph_part_data_structure_e::top_tree just put the edge to the set of edges that do not belong to the forest.

get_top_tree_internal_operations_selecting_path_t let augmented_graph_part_data_structure_e::top_tree order the set of edges that do not belong to the forest in weight-increasing order, so that when eraseing a tree edge, augmented_graph_part_data_structure_e::top_tree look for replacement among the edges in weight-increasing order.

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::less<void>>>
	>,
	monostate_comparator_t
> augmented_graph;

minimum_spanning_forests

Two augmented_graph_part_data_structure_e::top_trees are attached to the graph. Part-0 and part-1 maintain minimum spanning forest and maximum spanning forest of the graph respectively. Negating the comparator of minimum spanning forest configuration results in maximum spanning forest configuration.

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::less<void>>>,
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::greater<void>>>
	>,
	monostate_comparator_t
> augmented_graph;

tree_nearest_marked_vertexes

Each vertex_t(bool) stores whether the vertex is marked. Each edge_t(int) stores the length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, the nearest marked vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices) and distance to them for each its 2 boundary vertices. Quickly answers the nearest marked vertices to any vertex and its distance to them by exposeing the vertex and adding the information excluded. Quickly mark/unmark any vertex by exposeing the vertex (so that no cluster_t has the vertex as non-boundary descendant vertex) and updateing it. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	bool,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_nearest_marked_vertices_t<int>>
	>
> augmented_graph;

tree_diameter_and_centers

Each edge_t(int) stores the non-negative length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, eccentricity and 1 farthest vertex (through the cluster's descendant edges) for each its 2 boundary vertices, diameter and 2 farthest vertices (through the cluster's descendant edges). Quickly answers the eccentricity and 1 farthest vertex of any vertex by exposeing the vertex. Quickly answers the diameter and 2 farthest vertices of the graph because the information is stored in root cluster. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_diameter_t<int>>
	>,
	monostate_comparator_t
> augmented_graph;

tree_medians

Each vertex_t(int) stores the non-negative weight of the vertex. Each edge_t(int) stores the non-negative length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, distance-weighted weight sum of vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices) for each its 2 boundary vertices, weight sum of vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices). Quickly answers the median of the graph by non_local_searching choosing sub-cluster having larger weight sum of vertices (including its 2 boundary vertices) each round, exposeing the 2 vertices of the result edge and adding the information excluded. Quickly change the weight of any vertex by exposeing the vertex (so that no cluster_t has the vertex as non-boundary descendant vertex) and updateing it. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	int,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_median_t<int>>
	>
> augmented_graph;

tree_jump_and_meet

Each edge_t(int) stores the positive length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores tree path length between its 2 boundary vertices. Quickly answers: along the tree path between any 2 vertices, edge including any number (each edge includes range [0,l1), [l1,l1+l2), ..., or each edge includes range (0,l1], (l1,l1+l2], ...) starting from one of the vertex, by exposing the 2 vertices and searching among path descendant sub-clusters between the 2 vertices. Quickly answers the intersection vertex of any 3 vertices by exposing each of 3 vertex pairs and reading tree path length between each vertex pair from the root cluster, along the tree path between v1 and v2 calculating the 2 edges including number (d12+d13-d23)/2 using left-inclusive-right-exclusive view and left-exclusive-right-inclusive view respectively (the intersection vertex is the common vertex of the 2 edges). Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_distance_t<int>>
	>,
	monostate_comparator_t
> augmented_graph;